class code4 {
    //TOP k问题
    int[] ret;
    public int[] inventoryManagement(int[] nums, int k) {
        qsort(nums,k,0,nums.length-1);
        ret = new int[k];
        for(int i=0;i<k;i++) {
            ret[i] = nums[i];
        }
        return ret;
    }
    public void qsort(int[] nums,int k,int l,int r) {
        //出口
        if(l>=r) return;
        //分三组
        int left=l-1,right=r+1,i=l;
        int key = nums[l+new Random().nextInt(r-l+1)];
        while(i<right) {
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]==key) i++;
            else swap(nums,--right,i);
        }

        //2.分类讨论
        int a = left-l+1,b = right-left-1;
        if(k<=a)  qsort(nums,k,l,left);
        else if(b+a>=k) return;
        else qsort(nums,k-b-a,right,r);
    }
    public void swap(int[] nums,int a,int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}